/******* Locker problem solver *******
 * usage:
 *   given the number of lock and the number 
 *   of player, calculate the result of 
 *   "Locker Problem"
 * Create by Li ZHOU, March 31
 */

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>

#include <sys/wait.h>
/* for semaphore */
#include <limits.h>
#include <errno.h>
#include <sys/stat.h>
#include <sys/ipc.h>
#include <sys/sem.h>
/* for shm */
#include <sys/shm.h>
#include <sys/types.h>

/* const value */
#define SP_PERM ( S_IRUSR | S_IWUSR )							// semaphore permission
#define SHM_PERM ( S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP )	// shardMem permission
#define SET_SIZE 1                  // size of semaphore set 

/* obtain a semaphore and initialize to @init_value */
int get_semaphore(int init_value);
	
/* set the struct for semop */
void set_sembuf_struct ( struct sembuf *s, int num, int op, int flag );

/* remove semaphore from sys */
int remove_sem(int semid);

/* obtain id of a specific size shared mem */
int get_shmid(int size);

/* detach the shared memory */
int detach_shm(void * ptr);

/* P function */
int wait_sem(int sem_id);

/* V function */
int signal_sem(int sem_id);

void usage(char * s) {
	fprintf(stderr, "usage: %s [proc] [locker]\n", s);
}

/***************** Main Function ************************/
int main ( int argc, char * argv[] ) {
    
	int num_player = 0; // number of players
	int num_locker = 0; // number of lockers
	int i = 0;          // for loop 
    
	/* number of arguments error */
	if( argc != 3) {
		fprintf(stderr, "No arguments.\n");
		usage(argv[0]);
	    exit(1);
	}

	num_player = atoi(argv[1]) ;
	num_locker = atoi(argv[2]) ;

	/* Invalid value of arguments */
	if(num_player <= 0 || num_locker <= 0) {
        fprintf(stderr, "Arguments error. less than 0 or Invalid.\n");
		exit(1);
	}
	else {
		fprintf(stdout, "Total locker: %d; Total player: %d\n",
				num_locker, num_player);
	}
	/* too much players, causes idle proc */
    if( num_player > num_locker ) {
		fprintf(stderr, "too much players." 
				"It should less than the number of lockers.\n");
		exit(1);
	}
    /*********** Define Shared Mem Struct ***********/
	typedef struct {
		int round;             // record remainning round 
		short lock[ num_locker ]; // lock state
	} SHM;
	typedef SHM *SHM_PTR;

    /************ Get Semaphore  ****************/
    int sem_id_locker;
    sem_id_locker = get_semaphore(1);
    if(sem_id_locker < 0) {
		exit(1);
	}

	int sem_id_round;
	sem_id_round = get_semaphore(1);
	//get error
	if(sem_id_round < 0) {
		remove_sem(sem_id_locker);
		exit(1);
	}

	/************ Initialize Shared Memory ************/

    int shm_id;
	SHM_PTR ptr_shm;
    shm_id = get_shmid(sizeof(SHM));
	/* attach shared memory */
 	if( (ptr_shm = (SHM_PTR)shmat(shm_id, 0 , 0)) == (SHM_PTR)-1 ) {
		perror("shmat() failed in main: ");
		remove_sem(sem_id_locker);
		remove_sem(sem_id_round);
		exit(1);
	}

    /* Initialize the lockers to closed */
    for( i = 0; i < num_locker ; i++ ) {
		ptr_shm->lock[i] = 1;               // @true: cloased
    }
	ptr_shm->round = num_locker;

    /* Generate Player processes */
	pid_t pid;
	for(i = 0; i < num_player; i++ ) {
		if((pid = fork()) == 0) {
			fflush(stdout);
			break;
		}
		else
            fflush(stdout);
			//fprintf(stderr,"\tchild: %d created.\n", pid); 
	}

	/** child proc **/
    if( pid == 0 ) {
		int todo[num_locker];
        while(1) {
		    int current_round;
			wait_sem(sem_id_round);
			// no more round remaining 
			if(ptr_shm->round == 0) {
				signal_sem(sem_id_round);
				break;
			}
			// keep playing
			else {
			    ptr_shm->round--;
				current_round = num_locker - ptr_shm->round;
				signal_sem(sem_id_round);
			}
			/* obtain the array of to be flipped lock */
			memset(todo, 0, sizeof(todo));

			int to_do_items = (num_locker / current_round);
			for(i = 0; i < to_do_items; i++) {
				if(i == 0)
					todo[i] = 0 + current_round;
				else
				    todo[i] = todo[i-1] + current_round;
			} 
			wait_sem(sem_id_locker);
			for(i = 0; i < to_do_items; i++) 
				//flip lock
				ptr_shm->lock[ todo[i]-1 ] = (ptr_shm->lock[ todo[i]-1 ]? 0 : 1);
			signal_sem(sem_id_locker);
        }
	    /**** Cleaning the allocated resource ****/
		if(detach_shm((void *)ptr_shm) < 0)
			exit(3);
    }
    else {

		//waiting for the child processes finish
		int status = 0;
		
        while((pid = wait(&status)) ){
            if( (pid == -1) && (errno != EINTR) ) {
				break;
			}
			else {
				;//fprintf(stderr, "child: %d finished.\n", pid);
			}
            //to process abnormal return;
		}
        
		printf("\n\n*********** RESULT **********\n");
		/***** Get the final result *****/ 
		if( ptr_shm->round != 0 ){
			fprintf(stderr, "Unfinished Job. Remaining round: %d\n", ptr_shm->round);
			return -5;
		}
		int open_cnt = 0;
		int close_cnt = 0;
		// only keep 20 index of opened locks
		int rightmost_open[20] = {0} ;
		i = num_locker;
		
		/** statistic  info **/
		for(; i > 0; i-- ){
			if( ptr_shm->lock[i-1] )
				close_cnt++;
			else {
				if(open_cnt < 20)
					rightmost_open[open_cnt] = i;
				open_cnt++;
			}   
		}
		/** output **/
		fprintf(stdout, "Total open: %d; Total closed: %d\n",
				open_cnt, close_cnt);
		fprintf(stdout, "The rightmost 20 open lock is:\n");
		for(i = 0; i < 20; i++) {
			//only output valid info
			if(rightmost_open[i] > 0) 
				fprintf(stdout, "lock[ %d ] is open.\n", rightmost_open[i]);
		}

		// remove semaphore
		remove_sem(sem_id_locker);
		remove_sem(sem_id_round);
		// remove shared memory
		detach_shm((void *)ptr_shm);
		// detach shared memory
		shmctl(shm_id, IPC_RMID, (struct shmid_ds *)0);	// remove shared memory
	}
    exit(0);
}

int get_semaphore(int init_value) {
    int sem_id;
	/* get the semaphore id */
	if((sem_id = semget(IPC_PRIVATE, SET_SIZE, SP_PERM)) == -1) {
		fprintf(stderr, "[%ld]: couldn't get semaphore: %s\n",
				(long)getpid(), strerror(errno));
		return -1;
	}
    printf("\tObtain Semaphore.\n");
	/* initial the semaphore value */
	if( semctl(sem_id, 0, SETVAL, init_value) < 0 ) {
		perror("semctl(,SETVAL,)");
        remove_sem(sem_id);
		return -2;
	}
    printf("\tInitialize semaphore success.\n");
	return sem_id;
}


/* set_sembuf_struct for semop */
void set_sembuf_struct ( struct sembuf *s, int num, int op, int flag ) {
	s->sem_num = (short) num;  /* # of item in set */
	s->sem_op = op;            /* negative, 0 , positive */
	s->sem_flg = flag;          /* IPC_NOWAIT, SE<_UNDO .. */
	return;
}

/* Remove semaphore, only be called in main proc.
 * keep return value for patch 
 * */
int remove_sem(int sem_id ) {
    if(semctl(sem_id, 0, IPC_RMID) == -1 ) {
		fprintf(stderr, "[%ld] could not remove semaphore, %s\n",
			   (long)getpid(), strerror(errno));
		return -5;
	}
	printf("\tRemove sem: %d success.\n", sem_id);
	return 0;
}


int get_shmid(int size) {
	int shmid;
    if( (shmid = shmget(getpid(), size , IPC_CREAT | SHM_PERM )) < 0 ) {
		perror("shmget() failed. ");
		return -3;
	}
	printf("\tObtain shared memory id success.\n");
	return shmid;
}

int detach_shm(void * ptr) {
	if(shmdt(ptr) < 0 ) {
		perror("shmdt()");
		return -4;
	}
	printf("\tDetach shared memory success.\n"); 
	return 0;
}

int wait_sem(int sem_id) {
    struct sembuf semwait[1];
	set_sembuf_struct(semwait, 0, -1, 0 );
    if(semop(sem_id,semwait, 1) < 0 ) {
         perror("wait failed.");
		 exit(2);
    }
	return 0;
}

int signal_sem(int sem_id) {
    struct sembuf semsignal[1];
	set_sembuf_struct(semsignal, 0, 1, 0 );
    if( semop(sem_id, semsignal, 1) < 0 ) {
		perror("signal failed.");
		exit(2);
	}
	return 0;
}


